#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <iomanip>
#define INF 10000;

using namespace std;

/**
 *邻表法实现graph
 */
template<typename Object>
class graph_list
{  
private:
  class vertex;
  class edge
  {
  public:
    vertex *v;
    int weight;
    int direction;
    edge(){
      v = NULL;
      weight = 0;
      direction = -1;
    }
    
  };
  class vertex
  {
  public:
    string name;
    Object data;
    list<edge> edgeList;
    int dis; //到达源点的距离
    string path;
  };
   
  list<vertex> vertexList;
  
  typename list<vertex>::iterator itr;
  typename list<edge>::iterator itrEdge;

public:
  void insertVertex( const Object &in_data,const string &in_name )
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
	
	if( (*itr).name == in_name )
	  return;
      }//防止顶点重名
    
    vertex temp;
    temp.name = in_name;
    temp.data = in_data;
    vertexList.insert( vertexList.end(),temp );
  }

  
  void deleteVertex( const string &name )
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	if( (*itr).name == name)
	  break;
      }
    
    if( (*itr).name != name )
          return;                        //在graph中没有找到要删除的顶点，返回.
    
    
    typename list<edge>::iterator itrEdge_tmp;
    
    
    for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)//删除所有边连接的顶点中的
      {
	 for( itrEdge_tmp = (*itrEdge).v->edgeList.begin(); itrEdge_tmp != (*itrEdge).v->edgeList.end(); itrEdge_tmp++)
	    {
	      
	      if( (*itrEdge_tmp).v->name == (*itr).name)
		{
		  (*itrEdge).v->edgeList.erase( itrEdge_tmp );
		  break;
		}
	    }
	 
      }
    
    (*itr).edgeList.clear();    
    vertexList.erase( itr );
    
  }
  
  
  
  void setEdge( const string & a_name, const string & b_name,int in_weight )//建立一个从a指向b的边
  {
    
    edge tmp_edge;
    vertex *A;
    vertex *B;
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
       	
	if(  (*itr).name == a_name )
	  A = &(*itr);
	if( (*itr).name == b_name )
	  B = &(*itr);
	
      }
    
    for( itrEdge = A->edgeList.begin(); itrEdge != A->edgeList.end(); itrEdge++)
      {
	if( (*itrEdge).v->name == b_name )
	  {
	    deleteEdge(a_name, b_name);
	    break;
	  }
      }//如果图中已经存在这条边了，则将原来的边覆盖掉

    tmp_edge.v = B;
    tmp_edge.weight = in_weight;
    tmp_edge.direction = 1;   
    A->edgeList.push_back( tmp_edge );
    
    tmp_edge.v = A;
    tmp_edge.direction = 0;
    B->edgeList.push_back( tmp_edge );
    
  }
  
  void deleteEdge( const string & a_name, const string & b_name )
  {
    
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++ )
      {
	if( itr->name == a_name )
	  for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)
	    {
	      if( (*itrEdge).v->name == b_name)
		{
		  (*itr).edgeList.erase( itrEdge );
		  break;
		}
	    } //删掉a中存储的关于b的边
	
	if( itr->name == b_name )
	  for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++)
	    {
	      if( (*itrEdge).v->name == a_name)
		{
		  (*itr).edgeList.erase( itrEdge );
		  break;
		}
	    } //删掉b中存储的关于a的边	  
      }   
    
  }


  
  //void list(){}
   
 void listVertex()
  {
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	cout << (*itr).name << " : "<< (*itr).data << endl;
      }

  }
  
  void listEdge()
  {
    string output;    //将数据调整为想要的输出格式
    string revise_output;
    
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++ )
	  {
      	     if( (*itrEdge).direction )//只输出从当前结点指出的边，防止重复输出.无向图当成是对应两倍边长数的有向图.
	     {
		output = "(";
		output += (*itr).name;
		output +=", ";
		output += (*itrEdge).v->name;
		output +=", ";
		output += to_string( (*itrEdge).weight );
		output +=")";
	    
		cout<< output << " ";
		 }
	  }
					      
      }
  }

  int num_edges()
  {
    int NumEdges = 0;
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	for( itrEdge = (*itr).edgeList.begin(); itrEdge != (*itr).edgeList.end(); itrEdge++ )
	  {
	    if( (*itrEdge).direction )//防止对边重复计数
	     {
	       NumEdges++;
		
		 }
	  }
					      
      }
    return NumEdges;
  }

  int num_vertexs()
  {
    return vertexList.size();
  }

  void BellmanFord( string src )
  {
    int v = num_vertexs();
    int flag = 1;//用于确认图中有输入的点与提前结束松弛

    /**
     *初始化
     */
    for(itr = vertexList.begin(); itr !=vertexList.end(); itr++)
      {
	itr->dis = INF;
	if( itr->name == src)
	  {
	    flag = 0;
	    itr->dis = 0;
	    itr->path += itr->name;
	  }
	
      }     

    if( flag )
      {
	cout<<"There is no vertex named "<< src <<endl;
	return ;
      }

    /**
     *松弛
     */
    for( int i = 1; i < v; i++)
      {
	flag = 1;
	
	for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	
	for( itrEdge = itr->edgeList.begin(); itrEdge != itr->edgeList.end(); itrEdge++)
	  {
	    if( itrEdge->direction )
	      {
		if( itrEdge->v->dis > itr->dis + itrEdge->weight)
		  {
		    itrEdge->v->path = itr->path;
		    itrEdge->v->path += "->";
		    itrEdge->v->path += itrEdge->v->name;
		    itrEdge->v->dis = itr->dis + itrEdge->weight;
		    flag = 0; //记录松弛操作
		    
		  }
	      }
	  }

      }
	if( flag )
	  break; //这一次没有进行松弛，提前结束算法
      }

    /**
     *检测负边环
     */
    flag = 0;
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	
	for( itrEdge = itr->edgeList.begin(); itrEdge != itr->edgeList.end(); itrEdge++)
	  {
	    if( itrEdge->direction )
	      {
		if( itrEdge->v->dis > itr->dis + itrEdge->weight)
		  {
		    flag = 1;// 存在负边环
		    
		  }
	      }
	  }

      }

    
    if( flag )
      {
	cout <<"图中存在负边环"<< endl;
	  return;
      }

    cout <<"distances:"<< endl;
    for( itr = vertexList.begin(); itr != vertexList.end(); itr++)
      {
	cout << (*itr).name << ":"<< itr->dis <<", path: "<< itr->path<< endl;
      }

    return ;
    

  }
 
  
};






/**
 *邻接矩阵法实现GRAPH
 */		 
template<typename Object>
class graph_matrix 
{
private:
  
  class vertex{
  public:
    Object data;
    string name;
    int dis;//到达源点的距离
    string path;
  };
  
  
  vector<vertex> vertexList;

  int edge_matrix[1400][1400];//最大容量是200个顶点,之后再修改也ok
  
public:
  /**
   *初始化二维矩阵
   */
  graph_matrix(){
    for(int i=0; i < 21; i++)
      {
	for(int j=0; j < 21; j++)
	  {
	    edge_matrix[i][j] = 0;
	    
	  }
      }
    
  }

  void insertVertex( const Object &in_data, const string &in_name )
  {
    vertex temp;
    temp.name = in_name;
    temp.data = in_data;
    vertexList.push_back( temp );
  }
  
  void deleteVertex( const string &in_name )
  {
    int flag = 1;//用于记录是否在图中找到该顶点
    for( int i = 0; i < vertexList.size(); i++)
      {
	if( vertexList[i].name == in_name)
	  {
	    flag =0;
	    vertexList.erase( vertexList.begin() + i);
	    break;
	  }
      }
    
    if(flag)
      return;
    
    int i,j;
    
    for( i=0; i <= vertexList.size() ; i++)
      {
	for( j=0; j<= vertexList.size(); j++)
	  {
	    if( j >= flag)
	     edge_matrix[i][j] = edge_matrix[i][j+1];	 
	  }
      }

    
    for( i=0; i <= vertexList.size() ; i++)
      {
	for( j=0; j<= vertexList.size(); j++)
	  {
	    if( i >= flag)
	     edge_matrix[i][j] = edge_matrix[i+1][j];	 
	  }
      }
  }
  
  void setEdge( const string &a_name, const string &b_name, int in_weight )
  {
    int i=0,j=0,k=0;
    int flag_1=0, flag_2=0;
    
    for( k = 0 ; k < vertexList.size() ; k++)
      {
	if(vertexList[k].name == a_name)
	  i = k, flag_1 = 1;
	if(vertexList[k].name == b_name )
	  j = k, flag_2 = 1;	
      }
    
    if( flag_1 && flag_2 )//在顶点中找到输入的两个顶点才操作。否则直接返回
      {
	edge_matrix[i][j] = in_weight;
      }
    return;
  }
  
  void deleteEdge( const string & a_name, const string & b_name )
  {

    int i=0,j=0,k=0;
    int flag_1=0, flag_2=0;
    
    for( k=0; k < vertexList.size(); k++)
      {
	if(vertexList[k].name == a_name)
	  i = k, flag_1 = 1;
	if(vertexList[k].name == b_name )
	  j = k, flag_2 = 1;	
      }
    
    if( flag_1 && flag_2 )//在顶点中找到输入的两个顶点才操作。否则直接返回
      {
	edge_matrix[i][j] = 0;
      }
    return;
  }

  
  void listVertex()
  {
    for( int k =0; k < vertexList.size(); k++ )
      {
	
	  cout << vertexList[k].name << " : "<< vertexList[k].data << endl;
      }
  }
  
  void listEdge()
  {
    string output;
    int i,j; 
    
    
    for( i=0; i < vertexList.size() ; i++)
      {
	for( j=0; j < vertexList.size(); j++ )
	  if( edge_matrix[i][j] )
	    {
	      output = "(";
		output += vertexList[i].name;
		output +=", ";
		output += vertexList[j].name;
		output +=", ";
		output += to_string( edge_matrix[i][j] );
		output +=")";
	    
		cout<< output << " ";


	    }
      }

  }

  int num_edges()
  {
    int NumEdges = 0 ;
    int i,j; 
    
    
    for( i=0 ; i < vertexList.size(); i++ )
      {
	for( j=0 ; j < vertexList.size(); j++ )
	  if( edge_matrix[i][j] )
	    {
	      NumEdges++;
	    }
      }

    return NumEdges;
  }
  
  int num_vertexs()
  {
    return vertexList.size();
  }

  void BellmanFord( string src )
  {
    int v = num_vertexs();
    int flag = 1; //用于确认图中有输入的点与提前结束松弛
    int i,j,k; //之后取edge用时用来记录现在的顶点位置
    /**
     *初始化距离
     */
    for( i=0; i < vertexList.size(); i++)
      {
	vertexList[i].dis = INF;
	if( vertexList[i].name == src)
	  {
	    flag = 0;
	    vertexList[i].dis= 0;
	    vertexList[i].path = vertexList[i].name;
	  }
      }

    if(flag)
      {
	cout<< "There is no vertex named"<< src << endl;
	return;
      }
    
    /**
     *松弛
     */
    for( i = 1; i < v; i++)
      {
	flag = 1;
	
	for( j =0; j < v; j++)
	  {
	    for( k = 0; k < v; k++)
	      {
		if( edge_matrix[j][k] )
		  {
		    if( vertexList[k].dis > vertexList[j].dis + edge_matrix[j][k] )
		      {
			vertexList[k].path = vertexList[j].path;
			vertexList[k].path +="->";
			vertexList[k].path += vertexList[k].name;
			vertexList[k].dis = vertexList[j].dis + edge_matrix[j][k];
			flag = 0;
		      }
		  }
	      }



	  }
	if( flag ) //这一轮中没有松弛，提前结束循环
      	  break;
      }
    
    /**
     *检测负边环
     */
    flag =0;
    
    for( j =0; j < vertexList.size(); j++)
      {
	for( k = 0; k < v; k++)
	  {
	    if( edge_matrix[j][k] )
	      {
		if( vertexList[k].dis > vertexList[j].dis + edge_matrix[j][k] )
		  flag = 1; //出现负边环
	      }
	  }
      }

    if( flag )
      {
	cout << "图中存在负边环" << endl;
	return;
      }
    
    cout << "distances :"<<endl;
    for( i = 0; i < vertexList.size(); i++)
      {
	cout << vertexList[i].name <<":"<< vertexList[i].dis<<", path: "<<vertexList[i].path << endl;
      }
    
    return;
  }

};
